package com.zyk.java8;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangsan
 * @date 2021/5/12 19:41
 */
public class Test {

    // m1 [start, end][start, end] , 上班时间
    // m2 [start, end][start, end][start, end] 请假时间
    // 暴力解, 直接m2, 对m1进行遍历, 时间复杂度 O(M*N)
    public static List<int[]> validTime(int[][] m1, int[][] m2) {
        int N = m1.length;
        int M = m2.length;

        List<int[]> res = new ArrayList<>();

        for (int[] m2Time : m2) {
            for (int[] m1Time : m1) {
                if (m2Time[0] > m1Time[1]) {     // 请假开始时间 > 工作时间的结束时间
                    continue;
                } else if (m2Time[1] <= m1Time[1]) {
                    // 请假结束时间 在工作结束时间内

                    break;
                }
            }
        }


        return res;
    }

    // 位图.
    public static List<int[]> validTime2(int[][] m1, int[][] m2) {
        int[] status = new int[45];         // 1440 分钟
        for (int[] times : m1) {
            int start = times[0];
            int end = times[1];
            int index, path;
            for (int i = start; i <= end; i++) {    // 1 ~ 1440
                index = (i - 1) / 32;
                path = i % 32;
                status[index] |= (1 << path);
            }
        }
//        System.out.println("上班时间" + Arrays.toString(status));
        for (int[] times : m2) {
            int start = times[0];
            int end = times[1];
            int index, path;
            for (int i = start; i <= end; i++) {    // 1 ~ 1440
                index = (i - 1) / 32;
                path = i % 32;
                if ( ((status[index] >> path) & 1) == 1) {        // 如果是有效工作时间段, 给他变为0
                    status[index] ^= (1 << path);
                }
            }
        }
//        System.out.println("真正工作时间: " + Arrays.toString(status));

        List<int[]> res = new ArrayList<>();
        int index, path;
        for (int i = 1; i <= 1440; i++) {
            index = (i - 1) / 32;
            path = i % 32;
            if ( ((status[index] >> path) & 1) == 1) {
                int start = i;
                int end = 1440;
                while (++i <= 1440) {
                    index = (i - 1) / 32;
                    path = i % 32;
                    if ( (status[index] >> path & 1) == 0) {
                        end = i;
                        break;
                    }
                }
                res.add(new int[] {start, end});
            }
        }
        return res;
    }


    // for test
    public static void main(String[] args) {
        int[][] m1 = {
                {10 * 60, 12 * 60},
                {13 * 60, 20 * 60}
        };
        int[][] m2 = {
                {11 * 60 + 30, 14 * 60},
                {16 * 60, 20 * 60}
        };

        List<int[]> times = validTime2(m1, m2);
        System.out.println("有效上班时间段: ");
        for (int[] time : times) {
            System.out.println("开始时间: " + time[0] + ", 结束时间: " + time[1] );
        }

        // 719 / 60 = 72 / 6 = 12
        //
    }

}
